package sf.sort;

import java.util.Arrays;

/**
 * 快速排序
 * 选一个数，分成左右两组，左边小，右边大
 */
public class QuickSort implements Sort{

    @Override
    public void sort(int[] unsorted) {

        quickSort(unsorted, 0, unsorted.length);
    }

    public void quickSort(int[] unsorted, int l, int n) {
        // 退出条件？
        System.out.println(Arrays.toString(unsorted));
        if (n - l <= 1) {
            return;
        }
        final int num = unsorted[l];
        // 比num大的和比num小的
        int i = l;
        int j = n-1;
        while (i < j) {
            // 开始从后往前找
            while ((i < j) && (unsorted[j] > num)) {
                j --;
            }
            while ((i < j) && (unsorted[i] < num)) {
                i ++;
            }
            // 交换i与j
            if ((unsorted[i]==unsorted[j]) && (i < j)) {
                 i ++;
            } else {
                // 交换
                int temp = unsorted[j];
                unsorted[j] = unsorted[i];
                unsorted[i] = temp;
            }
        }
        if (i - 1 > l) quickSort(unsorted,l, i);
        if (j + 2 < n) quickSort(unsorted, j+1, n);
    }

}
